package DataStructure;
//稀疏表,支持"可重复的贡献"的问题的区间查询
public class SparseTable {
    //存储[i,i+2^j-1]的区间信息,由于任何区间都可以被分解为若干长度为2^k的子区间,则可以通过查询该表获取总区间信息
    private long[][] info;

    public SparseTable(long[] arr) {
        int n=arr.length;
        int m=Integer.bitCount(Integer.highestOneBit(n) - 1) + 1;//保证2^(m-1)<=n
        this.info=new long[n][m];
        //max[i,i]=i
        for (int i = 0; i < n; i++) {
            info[i][0]=arr[i];
        }
        //将区间平分,max[i,j]=max(max[i,j-1],max[i+2^(j-1),j-1])
        for (int j = 1; j < m; j++) {
            for (int i = 0; i + (1 << j) - 1 < n; i++) {
                info[i][j] = f(info[i][j - 1], info[i + (1 << (j - 1))][j - 1]);
            }
        }
    }

    //查询要求
    private long f(long a,long b){
        return Math.max(a,b);
    }

    public long query(int l,int r){
        //求出k满足2^k<=r-l+1<2^k+1,保证两个区间可以完全覆盖[l,r]
        int k = Integer.bitCount(Integer.highestOneBit(r - l + 1) - 1);
        return f(info[l][k], info[r - (1 << k) + 1][k]);
    }


}
